//
//  ProblemOffer68-1.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

 示例 1:
     输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     输出: 6
     解释: 节点 2 和节点 8 的最近公共祖先是 6。
 示例 2:
     输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     输出: 2
     解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 说明:
     所有节点的值都是唯一的。
     p、q 为不同节点且均存在于给定的二叉搜索树中。
 */
@objcMembers class ProblemOffer68_1: NSObject {
    func solution() {
        
    }
    // 因为是二叉搜索树：特点是：左 < 根 < 右
    // 如果p和q在root的左右2测，那么root就是答案
    
    // 迭代：我们的目标是要找到一个：p < root < q 或者 q < root < p 这样的节点
    // 如果root < p && root < q： 说明他们都在p和q的右侧，那么继续判断root.right是否正确
    // 如果root > p && root > q: 说明他们都在p和q的左侧，那么继续判断root.left是否正确
    // 其他情况就是p < root < q 或者 q < root < p：那么root就是答案
    func lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode) -> TreeNode? {
        var node = root
        while node != nil {
            if node!.val > p.val && node!.val > q.val {
                node = node?.left
            } else if node!.val < p.val && node!.val < q.val {
                node = node?.right
            } else {
                return node
            }
        }
        
        return root
    }
    
    // 迭代优化
    func lowestCommonAncestorYou(root: TreeNode?, p: TreeNode, q: TreeNode) -> TreeNode? {
        var minNode = p, maxNode = q
        if p.val > q.val {
            minNode = q
            maxNode = p
        }
        var node = root
        while node != nil {
            if node!.val > maxNode.val {
                node = node?.left
            } else if node!.val < minNode.val {
                node = node?.right
            } else {
                return node
            }
        }
        
        return root
    }
    
    // 递归
    func lowestCommonAncestorD(root: TreeNode?, p: TreeNode, q: TreeNode) -> TreeNode? {
        if root == nil {
            return root
        }
        if root!.val > p.val && root!.val > q.val {
            return lowestCommonAncestorD(root: root?.left, p: p, q: q)
        } else if root!.val < p.val && root!.val < q.val {
            return lowestCommonAncestorD(root: root?.right, p: p, q: q)
        } else {
            return root
        }
    }
}
